package library;

import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;

public class Prims {
	//If the size of the list is not the number of edges -1, then no mst can be formed
	public List<Edge> solve(PriorityQueue<Edge> pq){
		//This may be given if it is partially completed
		List<Edge> usedEdges = new LinkedList<Edge>();
		
		while (!pq.isEmpty()){
			Edge e = pq.poll();
			if (!e.begin.find(e.end)){
				e.begin.union(e.end);
				usedEdges.add(e);
			}
		}
		return usedEdges;
	}
	class Edge implements Comparable<Edge>{
		int weight;
		UnionFind begin,end;

		public Edge(UnionFind b,UnionFind e,int weight){
			this.begin=b;
			this.end=e;
			this.weight=weight;
		}
		@Override
		public int compareTo(Edge arg0) {
			if (weight < arg0.weight)
				return -1;
			else if (weight == arg0.weight)
				return 0;
			else
				return 1;
		}
	}
}